/**
 * 
 */
package name.marz.to.go.btree.node;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author masaru-gotou
 *
 */
public class BTree<E> {
	private Node root;

	/**
	 * @param root
	 */
	public BTree(Node root) {
		this.root = root;
	}

//	/**
//	 * 
//	 * @param keycount
//	 */
//	public BTree(int keycount) {
//		this.root = new ArrayNode(keycount);
//	}
	
	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	/**
	 * 指定されたキーでB木を検索する
	 * @param key
	 * @return 検索結果のオブジェクト。見つからない場合はnull
	 */
	@SuppressWarnings("unchecked")
	public E search(Key key) {
		Deque<Node> path = new ArrayDeque<Node>();	// 検索パススタック
		return (E)search(root,key,path);
	}
	private Object search(Node node, Key key, Deque<Node> path) {
		path.addFirst(node);
		Object p = node.getPointer(key);
		if ( p instanceof Node ) return search((Node)p,key,path);
		if ( node.hasKey(key) ) return p;
		return null;
	}
	
	/**
	 * データを挿入する<br>
	 * NodeクラスおよびNodeを継承するクラスのインスタンスをデータとして挿入することはできない。
	 * @param key
	 * @param data
	 */
	public void insert(Key key, Object data) {
		if ( data instanceof Node ) {
			throw new IllegalArgumentException(data+" is instance of Node. Node instance is NOT able to insert");
		}
		// 検索
		Deque<Node> path = new ArrayDeque<Node>();	// 検索パススタック
		search(root,key,path);
		
		// 検索パススタックのトップに入っているノード(=Leafノード)に、追加＆必要に応じて分割
		addAndSplit(key, data, path);
	}
	private void addAndSplit(Key key, Object data, Deque<Node> path) {
		// 検索パススタックからノードを取り出す
		Node node = path.removeFirst();
		try {
			// データを追加する
			node.add(key, data);
		} catch (NodeOverflowException e) {
			// 空き無しなので分割する
			Node larger_node = node.split();
			// 分割したどちらかに値を入れる
			if ( key.compareTo(larger_node.getFirstKey()) < 0 ) {
				add2Node(node,key, data);
			} else {
				add2Node(larger_node,key, data);
			}
			if ( path.size() == 0 ) {
				// rootなら新たなノードを生成しそれをあらたなrootとする
//				Node new_node = (Node)node.newNode();
				Node new_node = NodeFactory.createNode(node.getClass().getName(), node.getMaxKeys());
//				// rootが持っている値をコピー
//				for ( int i=0; i<node.getKeyCount(); i++ ) {
//					add2Node(new_node,node.getKey(i),node.getPointer(i));
//				}
//				new_node.setLeftPointer(node.getLeftPointer());
				// rootの中味を、分割元と分割先を指すようにセットする
//				node.clear();
				new_node.setLeftPointer(node);
//				node.setLeftPointer(new_node);
				add2Node(new_node,larger_node.getFirstKey(), larger_node);
				root = new_node;
			} else {
				// rootで無いなら、親にキーを追加＆必要なら分割
				addAndSplit(larger_node.getFirstKey(),larger_node,path);
			}
		}
	}
	
	private void add2Node(Node node, Key key, Object pointer) {
		try {
			node.add(key,pointer);
		} catch (NodeOverflowException e) {
			throw new InternalError("add failed");
		}
	}
}
